package leetcode.day_2020_12_14_12_21;

import com.sun.xml.internal.ws.policy.EffectiveAlternativeSelector;

/**
 * 剑指 Offer 55 - II. 平衡二叉树
 */
public class Offer_55 {
    public static void main(String[] args) {

    }

    /**
     * 后序遍历递归
     * @param root
     * @return
     */
    public static int judge_avl(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int left = judge_avl(root.left);
        if (left == -1) return -1;

        int right = judge_avl(root.right);
        if (right == -1) return -1;

        return Math.abs(left-right) < 2 ? Math.max(left, right) + 1 : -1;
    }

    /**
     * 递归求高度，递归判断左子树和右子树的
     * @param root
     * @return
     */
    public static boolean judge_avl2(TreeNode root) {
        if (root == null) {
            return true;
        }
        return Math.abs(height(root.left) - height(root.right)) < 2 && judge_avl2(root.left) && judge_avl2(root.right);
    }

    public static int height (TreeNode root) {
        if (root == null) {
            return 0;
        }
        int ld = height(root.left);
        int rd = height(root.right);
        return Math.max(ld, rd) + 1;
    }
}
